package 力扣._57_插入区间;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution2 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new LinkedList<>();
        int i;
        for (i = 0; i < intervals.length && newInterval[0] > intervals[i][1]; i++) ;
        for (int j = 0; j < i; j++) {   //i之前的全部添加
            result.add(intervals[j]);
        }
        if (i == intervals.length) {
            result.add(newInterval);
        } else {
            //找到结束位置
            int j;
            for (j = i; j < intervals.length && newInterval[1] > intervals[j][0]; j++) ;
            if (j == intervals.length)
                result.add(new int[]{Math.min(intervals[i][0], newInterval[0]), newInterval[1]});
            else {
                result.add(new int[]{Math.min(intervals[i][0], newInterval[0]), Math.max(intervals[j][1],newInterval[1])});
            }
            for (int k = j + 1; k < intervals.length; k++) {
                result.add(intervals[k]);
            }
        }
        return result.toArray(new int[result.size()][]);

    }

    public static void main(String[] args) {
//        int[][] insert = new Solution2().insert(new int[][]{{1,2},{3,5},{6,7},{8,10},{12,16}}, new int[]{4, 8});

        int[][] insert = new Solution2().insert(new int[][]{{1, 3}, {6, 9}}, new int[]{2, 5});
        System.out.println(Arrays.stream(insert).toList().toString());
    }
}
